Digital images and video frames are typically compressed in order to reduce data storage and transmission requirements. In most image compression methods, certain image data is selectively discarded to reduce the amount of data needed to represent the image, while avoiding substantial degradation of the appearance of the image.
FIG. 1 shows a flow diagram of a conventional method of processing an original image 10 to produce a compressed image 12. As shown in FIG. 1, a forward transform 14 is applied to the original image 10 to produce a set of forward transform coefficients 16. The forward transform 14 may be any type of transform that is operable to convert the original image 10 into a set of coefficients in a selected domain. A quantizer 18 is applied individually to the forward transform coefficients 16 to produce a set of quantized forward coefficients 20. The quantizer 18 discards some of the forward transform coefficient information, enabling the original image 10 to be compressed. An encoder 22 encodes the quantized forward transform coefficients using any type of lossless encoding technique to produce the compressed image 12.
The original image 10 may be a binary image (for instance, a dark and bright dot pattern), a multilevel single-color image (for instance, a gray-level image), or a multilevel multi-color image. In general, the image compression process of FIG. 1 is applied individually to each color plane of the original image 10.
FIG. 2 shows a flow diagram of a conventional block-transform-based image method of compressing an original image 10. As shown in FIG. 2, the original image 10 is initially converted into a preselected luminance-based color space (for instance, the YCrCb color space), if the original image 10 is not already specified in the preselected color space (block 24). Each color plane of the image in the preselected color space corresponds to a respective image (that is, an array of pixel values) that is processed individually as follows. The color components (for instance, the Cr and Cb color components) are downsampled (block 26). Each color plane is divided into blocks of pixels (for instance, 8×8 pixel blocks) (block 28). A block transform is applied to each pixel block individually (block 30). Any suitable type of block transform may be applied to the blocks. Exemplary types of block transforms include the cosine transform, Fourier transform, Hadamard transform, and Haar wavelet transform. The resulting transform coefficients are quantized (block 32). In addition, the quantized transform coefficients are encoded using a lossless coding technique to produce compressed image 12 (block 34).
To further illustrate the process depicted in FIG. 2, a particular example is provided in which the original image 10 is denoted as u and the compressed image 12 is denoted as f, which has been distorted during the compression process. The effect of the lossy part of a JPEG compression depends on the form of the block transform 30 used, which is characterized by a 64×64 2D-DCT transform matrix D and by an 8×8 quantization table Q. Both the transform matrix D and the quantization table Q are assumed to be known. In addition, the transform matrix D is typically the standard DCT-II transform, but it may be approximated in a form that may be implemented by fast integer-arithmetic as supported by the JPEG standard.
In this example, the following notations are used to mathematically describe the JPEG operation on image pixels of an image. The following notations are also used to describe the transform-domain filters employed later in the artifact reduction. The bold letters represent 2D indices, for instance, n=(nx,ny). JPEG divides the image having a size of (Nx,Ny) into 8×8 blocks. As such, each pixel-address n is split into a block index b and location within the block m, such that n=8b+m. The DCT coefficient index will be usually be denoted as k=(kx,ky). The output of the standard JPEG decoder f(b,m) at block b and relative location m is expressed as:
                                          f            ⁡                          (                              b                ,                m                            )                                =                                    ∑              k                        ⁢                                          D                                  m                  ,                  k                                t                            ⁢                                                Q                  k                                ⁡                                  [                                                            1                                              Q                        k                                                              ⁢                                                                  ∑                        j                                            ⁢                                                                        D                                                      k                            ,                            j                                                                          ⁢                                                  u                          ⁡                                                      (                                                          b                              ,                              j                                                        )                                                                                                                                ]                                            ⁢                              ∀                b                                                    ,                            Equation        ⁢                                  ⁢                  (          1          )                    where the square brackets indicate that the values contained therein are to be rounded to the nearest integer.
The quantization of the DCT coefficients 32 tends to generate mainly two types of artifacts, blocking and ringing artifacts. In blocks containing strong features (for instance, edges, lines, etc.), there is typically a large percentage of high frequency DCT components with substantial magnitudes. Some of these coefficients may fall under the relative quantization thresholds, thereby being zeroed out, while others survive. The unbalanced combination of post-quantization high-frequency components leaves patterns called “mosquito” or “ringing” artifacts, which resemble DCT-basis components. Ringing artifacts are more probable in pixels around a block center than in pixels near block-boundaries. Blocking artifacts generally originate from the fact that the quantization errors for pixels belonging to two neighboring blocks are not correlated. Blocking artifacts are known to originate mainly from quantization errors related to lower-frequency components, and to occur mainly near block boundaries.
Various image restoration algorithms have been proposed to overcome these image artifacts. One class of image restoration algorithms referred to as “overcomplete transform-domain filtering” is known to reduce blocking artifacts due to its ability to approximately restore the translation invariance of local-differences in the image statistics (the translation invariance was lost by the block-transform coding). The principle under these algorithms is to apply block-transform filters with block-grids aligned on different positions (shifts), and then to average the resulting outputs, which has been referred to as so-called “cycle-spinning” approach.
In a shifted block-grid, every pixel address n can be expressed by the shift s to the first block boundary, the block index b and location within the block m in the following fashion: ns=8b+m+s. A block-transform filter is defined by the block-transform T employed and by a set of non-linear mappings ψk that are each applied to their corresponding transform coefficient k. The mappings may correspond, for example, to soft or hard thresholding or quantization, and each of them is characterized by some scale parameter σk. Hence a block-transform filter with block boundaries at shift s is given by:ûs(b,m)=ΣkTm,ktψk(σk∥ΣjTk,jfs(b,j))∀b,s.  Equation (2):The output of the cycle-spinning filter at each pixel is given by spatially averaging contributions from all shifts.
Unfortunately, the so-called “cycle-spinning” approach only partially reduces the ringing artifacts since in the shifts that contain a strong edge, the block-transform filter does not reduce ringing effectively. In addition, the surviving artifacts in these shifts are averaged into the final result, thus leaving residual ringing artifacts.
Guleryuz proposed a solution to this problem in the context of image denoising by introducing selectivity into the averaging process in order to reject “bad shifts”. See, O. G. Guleryuz, “Weighted Overcomplete Denoising”, “Conference Record of the Thirty-Seventh Asilomar Conference on Signals, Systems and Computers,” Nov. 9-12, 2003, Vol. 2, pp. 1992-1996, and also U.S. Patent Application Publication No. 2004/0240545(A1) to Guleryuz. More particularly, Guleryuz introduced per-pixel weighting of shifts, where the weights were determined by formulating the weighted combination as a linear estimation problem and solving it for the individual pixel-wise weight factors. Guleryuz's solution employs many statistical assumptions and approximations that are valid only for independent identically distributed (i.i.d.) noise. Guleryuz's solution, however, is not suitable for JPEG images since the statistics of the distortion corresponding to JPEG compression artifacts due to transform coefficient quantization are both spatially varying and signal dependent, namely, non-i.i.d.
An improved approach to eliminating compression artifacts in images, and more particularly, in JPEG images would therefore be beneficial.